// https://leetcode.cn/problems/merge-k-sorted-lists/submissions/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// class Solution {
// public:
//     ListNode* mergeSort(ListNode* l1, ListNode* l2) {
//         ListNode* dummy = new ListNode(-1);
//         ListNode* tmp = dummy;
//         while (l1 && l2) {
//             if (l1->val < l2->val) {
//                 tmp->next = l1;
//                 l1 = l1->next;
//             } else {
//                 tmp->next = l2;
//                 l2 = l2->next;
//             }
//             tmp = tmp->next;
//         }
//         if (l1) tmp->next = l1;
//         if (l2) tmp->next = l2;
//         return dummy->next;
//     }
//     ListNode* merge(vector<ListNode*>& lists, int l, int r) {
//         if (l == r) return lists[l];
//         if (lists.empty()) return NULL;
//         int mid = (r - l) / 2 + l;
//         ListNode* left = merge(lists, l, mid);
//         ListNode* right = merge(lists, mid + 1, r);
//         return mergeSort(left, right);
//     }
//     ListNode* mergeKLists(vector<ListNode*>& lists) {
//         int l = 0;
//         int r = lists.size() - 1;
//         return merge(lists, l, r);
//     }
// };

struct cmp {
    // bool operator<(ListNode* a, ListNode* b) {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        ListNode* dummy = new ListNode(-1);
        ListNode* tmp = dummy;
        for (auto& t: lists) {
            if (t) q.push(t);
        }
        while (!q.empty()) {
            // ListNode* t = q.front();
            ListNode* t = q.top();
            q.pop();
            tmp->next = t;
            tmp = tmp->next;
            if (t->next) q.push(t->next);
        }
        return dummy->next;
    }
};